package com.yanceysong.codetop.s61_s70;

import java.util.Deque;
import java.util.LinkedList;

public class S62_Easy_155_最小栈 {
    // 使用两个栈：dataStack 保存所有数据；minTrackingStack 保存对应位置的当前最小值
    // 这样每次 push/pop 都能在 O(1) 时间更新最小值。
    private final Deque<Integer> dataStack;          // 存放真实元素
    private final Deque<Integer> minTrackingStack;   // 存放到当前栈深度时的最小值（与 dataStack 同步增长/缩减）

    /**
     * .S62_Easy_155_最小栈
     * .<p>
     * .题目链接：<a href="https://leetcode.cn/problems/min-stack/">https://leetcode.cn/problems/min-stack/</a>
     * .<p>
     * .题目描述：
     * .设计一个支持以下操作的栈，并能在常数时间内检索到当前栈中的最小元素：
     * .1. push(int val) 将元素 val 压入栈中
     * .2. pop() 移除栈顶元素
     * .3. top() 获取栈顶元素
     * .4. getMin() 检索当前栈中的最小元素
     * .<p>
     * .示例操作（来自 LeetCode）：
     * .输入：
     * .MinStack minStack = new MinStack();
     * .minStack.push(-2);
     * .minStack.push(0);
     * .minStack.push(-3);
     * .minStack.getMin();   // 返回 -3
     * .minStack.pop();
     * .minStack.top();      // 返回 0
     * .minStack.getMin();   // 返回 -2
     * .<p>
     * .核心标签：栈 / 设计数据结构 / 辅助栈 / 常数时间查询最值
     * .<p>
     * .解题思路（双栈法）：
     * .- dataStack 按顺序存放所有压入的值。
     * .- minTrackingStack 的栈顶始终是当前 dataStack 中的最小值。
     * .- 每次 push：将新值压入 dataStack，同时将 Math.min(当前最小值, 新值) 压入 minTrackingStack。
     * .- 每次 pop：两个栈同时弹出（保证同步）。
     * .- getMin：直接返回 minTrackingStack 栈顶。
     * .<p>
     * .为什么需要与 dataStack 一一对应？
     * .- 如果只在出现更小值时才往 minTrackingStack 压入，会在弹出非最小值时无法知道新的最小值。
     * .- 一一对应能保证任意时刻直接读取栈顶就得到当前最小值，无需回溯或额外逻辑。
     * .<p>
     * .ASCII 操作示例：
     * .操作序列: push(2), push(0), push(3), push(0), getMin(), pop(), getMin(), pop(), getMin()
     * .过程：
     * .步骤      dataStack           minTrackingStack(最小值轨迹)    当前最小
     * .push(2):  [2]                [∞,2] (∞为哨兵)                2
     * .push(0):  [0,2]              [∞,2,0]                       0
     * .push(3):  [3,0,2]            [∞,2,0,0]                     0
     * .push(0):  [0,3,0,2]          [∞,2,0,0,0]                   0
     * .getMin:   -> 返回 0
     * .pop():    弹出 0            弹出 0                         0
     * .getMin:   -> 返回 0
     * .pop():    弹出 3            弹出 0                         0
     * .getMin:   -> 返回 0
     * .<p>
     * .关键洞察：
     * .- 用“影子栈”同步保存每一层的最小值。
     * .- 初始化时可放入 Integer.MAX_VALUE 作为哨兵，避免空栈判断分支。
     * .- 也可使用单栈存储 (value, 当前最小) 的二元组；或者使用差值编码法（更复杂，需处理溢出）。
     * .<p>
     * .复杂度分析：
     * .- 时间复杂度：所有操作均为 O(1)。
     * .- 空间复杂度：O(n)，n 为已压入的元素个数（辅助栈与数据栈等长）。
     * .<p>
     * .拓展思考：如果需要同时支持 getMax()，可以再增加一个最大栈；或存储三元组 (value, minSoFar, maxSoFar)。
     */
    public S62_Easy_155_最小栈() {
        // 初始化两个栈，并在最小栈放入哨兵值，确保后续 minTrackingStack.peek() 总是有值
        dataStack = new LinkedList<>();
        minTrackingStack = new LinkedList<>();
        minTrackingStack.push(Integer.MAX_VALUE); // 哨兵，代表“当前还没有真实元素”
    }

    /**
     * .压栈操作：同步更新最小值轨迹栈。
     * .@param x 压入的元素
     */
    public void push(int x) {
        dataStack.push(x);
        // 新的最小值 = min(之前的最小值, 当前元素)
        minTrackingStack.push(Math.min(minTrackingStack.peek(), x));
    }

    /**
     * .弹栈操作：两个栈同时弹出，保持栈深一致。
     */
    public void pop() {
        // 假设根据题目使用场景，调用者保证栈不为空（若需要可加判空）
        dataStack.pop();
        minTrackingStack.pop();
    }

    /**
     * .返回当前栈顶元素。
     */
    public int top() {
        return dataStack.peek();
    }

    /**
     * .返回当前栈的最小元素。
     */
    public int getMin() {
        return minTrackingStack.peek();
    }

    // ===================== 测试代码区域 =====================
    public static void main(String[] args) {
        System.out.println("=== 最小栈功能测试开始 ===\n");

        // 测试1：题目示例
        testLeetCodeExample();

        // 测试2：严格递增序列
        testIncreasingSequence();

        // 测试3：严格递减序列
        testDecreasingSequence();

        // 测试4：包含重复最小值
        testDuplicateMinValues();

        // 测试5：包含负数与零
        testNegativeAndZero();

        // 测试6：交替出现更小值
        testAlternatingMin();

        // 测试7：单元素栈的操作
        testSingleElement();

        // 测试8：多次 pop 回退最小值
        testPopBacktrackMin();

        // 测试9：压力测试 (大量 push/pop)
        testStress();

        // 测试10：与单栈二元组实现的结果一致性 (可选比较)
        testConsistencyWithPairImplementation();

        System.out.println("\n=== 所有测试完成 ===");
    }

    // 测试1：题目示例
    private static void testLeetCodeExample() {
        System.out.println("--- 测试1: 题目示例 ---");
        S62_Easy_155_最小栈 minStack = new S62_Easy_155_最小栈();
        minStack.push(-2);
        minStack.push(0);
        minStack.push(-3);
        int m1 = minStack.getMin();
        assert m1 == -3 : "期望最小值 -3";
        minStack.pop();
        int top = minStack.top();
        assert top == 0 : "期望栈顶 0";
        int m2 = minStack.getMin();
        assert m2 == -2 : "期望最小值 -2";
        System.out.println("getMin()->-3, pop(), top()->0, getMin()->-2 ✓");
    }

    // 测试2：递增序列
    private static void testIncreasingSequence() {
        System.out.println("\n--- 测试2: 严格递增序列 ---");
        S62_Easy_155_最小栈 ms = new S62_Easy_155_最小栈();
        for (int i = 1; i <= 5; i++) {
            ms.push(i);
            assert ms.getMin() == 1 : "最小值应始终为1";
        }
        System.out.println("push 1..5 最小值始终为1 ✓");
    }

    // 测试3：递减序列
    private static void testDecreasingSequence() {
        System.out.println("\n--- 测试3: 严格递减序列 ---");
        S62_Easy_155_最小栈 ms = new S62_Easy_155_最小栈();
        for (int i = 5; i >= 1; i--) {
            ms.push(i);
            assert ms.getMin() == i : "最小值应为当前压入的 i";
        }
        System.out.println("push 5..1 过程中最小值依次变为5,4,3,2,1 ✓");
    }

    // 测试4：重复最小值
    private static void testDuplicateMinValues() {
        System.out.println("\n--- 测试4: 重复最小值 ---");
        S62_Easy_155_最小栈 ms = new S62_Easy_155_最小栈();
        ms.push(3);
        ms.push(1);
        ms.push(1);
        ms.push(2);
        assert ms.getMin() == 1 : "最小值应为1";
        ms.pop(); // 弹出2
        assert ms.getMin() == 1 : "最小值仍应为1";
        ms.pop(); // 弹出1 (第二个1)
        assert ms.getMin() == 1 : "最小值仍应为1 (还有一个1)";
        ms.pop(); // 弹出1 (第一个1)
        assert ms.getMin() == 3 : "最小值应回升到3";
        System.out.println("重复最小值压入与回退正确 ✓");
    }

    // 测试5：负数与零
    private static void testNegativeAndZero() {
        System.out.println("\n--- 测试5: 包含负数与零 ---");
        S62_Easy_155_最小栈 ms = new S62_Easy_155_最小栈();
        int[] arr = {0, -1, -1, -5, 10, -2};
        int[] expectedMins = {0, -1, -1, -5, -5, -5};
        for (int i = 0; i < arr.length; i++) {
            ms.push(arr[i]);
            assert ms.getMin() == expectedMins[i] : "最小值不匹配";
        }
        System.out.println("含负数序列最小值轨迹正确 ✓");
    }

    // 测试6：交替出现更小值
    private static void testAlternatingMin() {
        System.out.println("\n--- 测试6: 交替出现更小值 ---");
        S62_Easy_155_最小栈 ms = new S62_Easy_155_最小栈();
        ms.push(5); // min=5
        ms.push(3); // min=3
        ms.push(4); // min=3
        ms.push(2); // min=2
        ms.push(6); // min=2
        ms.push(1); // min=1
        assert ms.getMin() == 1 : "最小值应为1";
        ms.pop(); // 弹出1 -> min=2
        assert ms.getMin() == 2 : "最小值回退到2";
        ms.pop(); // 弹出6 -> min=2
        assert ms.getMin() == 2 : "最小值仍为2";
        ms.pop(); // 弹出2 -> min=3
        assert ms.getMin() == 3 : "最小值回退到3";
        System.out.println("交替最小值回退轨迹正确 ✓");
    }

    // 测试7：单元素栈
    private static void testSingleElement() {
        System.out.println("\n--- 测试7: 单元素栈 ---");
        S62_Easy_155_最小栈 ms = new S62_Easy_155_最小栈();
        ms.push(42);
        assert ms.top() == 42 : "栈顶应为42";
        assert ms.getMin() == 42 : "最小值应为42";
        ms.pop();
        // 弹出后如果再调用 top/getMin 会出错（题目默认不做非法调用）。此处不测试异常场景。
        System.out.println("单元素入栈 -> 栈顶与最小值一致 ✓");
    }

    // 测试8：多次 pop 回退最小值
    private static void testPopBacktrackMin() {
        System.out.println("\n--- 测试8: 多次 pop 回退最小值 ---");
        S62_Easy_155_最小栈 ms = new S62_Easy_155_最小栈();
        int[] arr = {7, 6, 5, 1, 2, 1};
        for (int v : arr) ms.push(v);
        // 当前最小应为1
        assert ms.getMin() == 1 : "最小值应为1";
        ms.pop(); // 弹出1 -> 仍有1
        assert ms.getMin() == 1 : "最小值应仍为1";
        ms.pop(); // 弹出2 -> 仍有1
        assert ms.getMin() == 1 : "最小值应仍为1";
        ms.pop(); // 弹出1 -> 最小值回升
        assert ms.getMin() == 5 : "最小值应回升到5";
        System.out.println("连续回退最小值行为正确 ✓");
    }

    // 测试9：压力测试
    private static void testStress() {
        System.out.println("\n--- 测试9: 压力测试 (大量 push/pop) ---");
        S62_Easy_155_最小栈 ms = new S62_Easy_155_最小栈();
        int n = 2000; // 适度，不要太大
        for (int i = 0; i < n; i++) {
            ms.push(i - 1000); // 值范围包含负数
        }
        assert ms.getMin() == -1000 : "最小值应为-1000";
        for (int i = 0; i < 500; i++) { // 弹出500个元素
            ms.pop();
        }
        assert ms.getMin() == -1000 : "最小值仍应为-1000";
        // 继续弹到最小值那一层
        for (int i = 0; i < 500; i++) {
            ms.pop();
        }
        // 现在最小值应回升到 -500
        assert ms.getMin() == -500 : "最小值应回升到-500";
        System.out.println("压力测试通过 (最小值轨迹正确) ✓");
    }

    // 测试10：与单栈(pair)实现一致性（简易对比）
    private static void testConsistencyWithPairImplementation() {
        System.out.println("\n--- 测试10: 与二元组实现一致性 ---");
        // 简单单栈二元组写法（仅用于对比，不作为主实现）
        class PairMinStack {
            private final Deque<int[]> stack = new LinkedList<>(); // int[]{value, minSoFar}
            void push(int x) {
                if (stack.isEmpty()) {
                    stack.push(new int[]{x, x});
                } else {
                    stack.push(new int[]{x, Math.min(stack.peek()[1], x)});
                }
            }
            void pop() { stack.pop(); }
            int top() { return stack.peek()[0]; }
            int getMin() { return stack.peek()[1]; }
        }
        S62_Easy_155_最小栈 ms1 = new S62_Easy_155_最小栈();
        PairMinStack ms2 = new PairMinStack();
        int[] ops = {5, 3, 7, 3, 2, 2, 9};
        for (int v : ops) {
            ms1.push(v);
            ms2.push(v);
            assert ms1.getMin() == ms2.getMin() : "两种实现最小值不一致";
        }
        for (int i = 0; i < 3; i++) { // 弹出三次比对
            ms1.pop(); ms2.pop();
            assert ms1.getMin() == ms2.getMin() : "弹出后最小值不一致";
        }
        System.out.println("双栈实现与二元组实现最小值一致 ✓");
    }
}
